#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INIT_SIZE 10        // 初始化表长
#define INCREMENT_SIZE 5    // 分配增量

typedef int Status;
typedef int Elemtype;

/*
 * 存储结构
 */
typedef struct{
    Elemtype *elem;    // 存储空间基址
    int length;        // 当前长度
    int size;        // 当前分配的表长大小
}SqList;

/*
 * 初始化一个空的线性表
 */
Status InitList(SqList *L){
    L->elem = (Elemtype *)malloc(INIT_SIZE * sizeof(Elemtype));
    if (!L->elem){
        return ERROR;
    }
    L->length = 0; // 初始化表长为 0
    L->size = INIT_SIZE; //初始化表大小
    return OK;
}

/*
 * 销毁线性表
 */
Status DestroyList(SqList *L){
    free(L->elem); // 释放内存
    L->length = 0;
    L->size = 0;
    return OK;
}

/*
 * 清空线性表
 */
Status ClearList(SqList *L){
    L->length = 0;
    return OK;
}

/*
 * 判断线性表是否为空
 */
Status isEmpty(const SqList L){
    if (0 == L.length){
        return TRUE; // 为空返回 TRUE
    }
    else{
        return FALSE; // 不为空返回 FALSE
    }
}

/*
 * 获取长度
 */
Status getLength(const SqList L){
    return L.length;
}

/*
 * 根据位置获取元素
 */
Status GetElem(const SqList L, int i, Elemtype *e){
    if (i < 1 || i > L.length){ // 判断位置是否超出范围
        return ERROR;
    }
    *e = L.elem[i-1];
    return OK;
}

/*
 * 比较两个元素是否相等
 */
Status compare(Elemtype e1, Elemtype e2){
    if (e1 == e2){
        return 0;
    }
    else if (e1 < e2){
        return -1;
    }
    else{
        return 1;
    }
}

/*
 * 查找元素
 */
Status FindElem(const SqList L, Elemtype e, Status (*compare)(Elemtype, Elemtype)){
    int i;
    for (i = 0; i < L.length; i++){
        if (!(*compare)(L.elem[i], e)){
            return i + 1;
        }
    }
    if (i >= L.length){
        return ERROR;
    }
}

/*
 * 查找前驱元素
 */
Status PreElem(const SqList L, Elemtype cur_e, Elemtype *pre_e){
    int i;
    for (i = 0; i < L.length; i++){ // 按位置迭代元素查找
        if (cur_e == L.elem[i]){
            if (i != 0){
                *pre_e = L.elem[i - 1];
            }
            else{
                return ERROR;
            }
        }
    }
    if (i >= L.length){ // 元素无此前驱元素
        return ERROR;
    }
}

/*
 * 查找后继元素
 */
Status NextElem(const SqList L, Elemtype cur_e, Elemtype *next_e){
    int i;
    for (i = 0; i < L.length; i++){
        if (cur_e == L.elem[i]){
            if (i < L.length - 1){
                *next_e = L.elem[i + 1];
                return OK;
            }
            else{
                return ERROR;
            }
        }
    }
    if (i >= L.length){
        return ERROR;
    }
}

/*
 * 插入元素
 */
Status InsertElem(SqList *L, int i, Elemtype e){
    Elemtype *new;
    if (i < 1 || i > L->length + 1){ // 先判断插入的位置是否符合元素长度的要求
        return ERROR;
    }
    if (L->length >= L->size){
        new = (Elemtype*) realloc(L->elem, (L->size + INCREMENT_SIZE) * sizeof(Elemtype));
        if (!new){
            return ERROR;
        }
        L->elem = new;
        L->size += INCREMENT_SIZE;
    }
    // 插入元素并讲之后的元素后移
    Elemtype *p = &L->elem[i - 1];
    Elemtype *q = &L->elem[L->length - 1];
    for (; q >= p; q--){
        *(q + 1) = *q;
    }
    *p = e;
    ++L->length;
    return OK;
}

/*
 * 删除元素并返回其值
 */
Status DeleteElem(SqList *L, int i, Elemtype *e){
    if (i < 1 || i > L->length){
        return ERROR;
    }
    Elemtype *p = &L->elem[i - 1];
    *e = *p;
    for (; p < &L->elem[L->length - 1]; p++){
        *(p) = *(p + 1);
    }
    --L->length; // 删除后表长减一
    return OK;
}

/*
 * 访问元素
 */
void visit(Elemtype e){
    printf("%d ", e);
}

/*
 * 遍历线性表
 */
Status TraverseList(const SqList L, void (*visit)(Elemtype)){
    int i;
    for(i = 0; i < L.length; i++){
        visit(L.elem[i]);
    }
    return OK;
}

/*
 * 主函数测试
 */
int main(){
    SqList L;
    if (InitList(&L)){ // 初始化顺序表
        Elemtype e;
        printf("init_success\n");
        int i;
        for (i = 0; i < 10; i++){
            InsertElem(&L, i + 1, i); // 插入元素
        }
        printf("length is %d\n", getLength(L));
        if (GetElem(L, 1, &e)) { // 获取第一个元素值
            printf("The first element is %d\n", e);
        }
        else{
            printf("element is not exist\n");
        }
        if (isEmpty(L)){ // 判断线性表是否为空
            printf("list is empty\n");
        }
        else{
            printf("list is not empty\n");
        }
        printf("The 5 at %d\n", FindElem(L, 5, *compare));
        PreElem(L, 6, &e); // 查找元素 6 的前驱元素
        printf("The 6's previous element is %d\n", e);
        NextElem(L, 6, &e); // 查找元素 6 的后继元素
        printf("The 6's next element is %d\n", e);
        DeleteElem(&L, 1, &e); // 删除 1 元素
        printf("delete first element is %d\n", e);
        printf("list:");
        TraverseList(L,visit);
        if (DestroyList(&L)){ // 销毁线性表
            printf("\ndestroy_success\n");
        }
    }
}